/* 
    时间复杂度最差情况为O(N^2)，较理想的是Nlog(N
        )，类似分水岭问题，只不过要进行递归
*/
var sortArray = function (nums) {
    if (nums.length < 2) return nums;
    return quickSort(nums, 0, nums.length - 1);
};

function quickSort(nums, left, right) {
    if (left >= right) return;

    let pivotIndex = partition(nums, left, right);
    quickSort(nums, left, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, right);
    return nums;
}

function partition(nums, left, right) {
    let pivot = right;
    let leftIndex = left;
    for (let i = left; i < right; i++) {
        if (nums[i] < nums[pivot]) {
            // 比较大小交换位置
            let temp = nums[i];
            nums[i] = nums[leftIndex];
            nums[leftIndex] = temp;
            leftIndex++;
        }
    }
    // 将末尾元素与比自己大的第一个元素交换位置
    [nums[leftIndex], nums[pivot]] = [nums[pivot], nums[leftIndex]];
    return leftIndex;
}

let arr = [1, 56, 5, 656, 32, 9, 2, 355, 565623, 5565, 56, 56, 56565, 5612, 545, 56];
let res = sortArray(arr);
console.log(res);
